package com.ly.algorithm.DataStructures.problem;

import java.util.Arrays;

/**
 * @Classname Dijkstra
 * @Description TODO
 * @Date 2020/5/4 23:15
 * @Author 冷心影翼
 */
public class Dijkstra {

    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G'};
        Graph3 graph = new Graph3(data);
        graph.insertVerxs(0,1,5);
        graph.insertVerxs(0,2,7);
        graph.insertVerxs(0,6,2);
        graph.insertVerxs(1,3,9);
        graph.insertVerxs(1,6,3);
        graph.insertVerxs(2,3,8);
        graph.insertVerxs(3,5,4);
        graph.insertVerxs(4,5,5);
        graph.insertVerxs(4,6,4);
        graph.insertVerxs(4,5,5);
        graph.insertVerxs(5,6,6);
        graph.showGraph();
        graph.dsj(6);
        System.out.println(Arrays.toString(graph.visitedVertex.alreadyArr));
        System.out.println(Arrays.toString(graph.visitedVertex.preVisited));
        System.out.println(Arrays.toString(graph.visitedVertex.dis));
    }
}

class Graph3 {
    private char[] vertex;
    private int[][] matrix;
    VisitedVertex visitedVertex;

    public Graph3(char[] vertex) {
        this.vertex = vertex;
        matrix = new int [vertex.length][vertex.length];
        final int N = 65535;
        for (int[] r: matrix) {
            Arrays.fill(r,N);
        }
    }

    public void insertVerxs(int i, int j, int w) {
        matrix[i][j] = w;
        matrix[j][i] = w;
    }

    public void showGraph() {
        for(int[] r:matrix) {
            System.out.println(Arrays.toString(r));
        }
    }

    public void dsj(int index) {
        visitedVertex = new VisitedVertex(vertex.length,index);
        update(index);

        for (int i=1;i<visitedVertex.alreadyArr.length;i++) {
            index = findNext();
            update(index);
        }
    }

    private void update(int index) {
        int len = 0;

        for(int i=0;i<matrix[index].length;i++) {
            len = visitedVertex.dis[index] + matrix[index][i];
            if(!visitedVertex.in(i) && len < visitedVertex.dis[i]) {
                visitedVertex.updatePre(i,index);
                visitedVertex.updateDis(i,len);
            }
        }

        visitedVertex.alreadyArr[index] = 1;
    }


    public int findNext() {
        int min = 65535;
        int index = 0;
        for(int i=0;i<visitedVertex.alreadyArr.length;i++) {
            if(!visitedVertex.in(i) && visitedVertex.dis[i]<min) {
                min = visitedVertex.dis[i];
                index = i;
            }
        }

        return index;
    }
}

class VisitedVertex {
    public int[] alreadyArr;

    public int[] preVisited;

    public int[] dis;

    public VisitedVertex(int length,int index) {
        this.alreadyArr = new int[length];
        this.preVisited = new int[length];
        this.dis = new int[length];
        Arrays.fill(dis,65535);
        dis[index] = 0;
    }

    public boolean in(int index) {
        return alreadyArr[index] == 1;
    }

    public void updateDis(int index,int length) {
        dis[index] = length;
    }

    public void updatePre(int pre,int index) {
        preVisited[pre] = index;
    }
}